# 将1到3999数字转变成对应的罗马数字表示，但是有6个特例是需要特殊表示的。
# 而且，如果某个数字是由这个6个特例数字组成或者部分组成，那么也需要表示成特例形式。如1994，994
class Solution:
    s = ''

    def intToRoman(self, num: int) -> str:
        if num < 1 or num > 3999:
            return '0'
        self.selectRank(num, self.isInstance(num))
        return self.s

    def isInstance(self, o) -> bool:
        instanceArr = [4, 9, 40, 90, 400, 900]
        return instanceArr.__contains__(o) or instanceArr.__contains__(int(o / 10)) or instanceArr.__contains__(
            int(o / 100))

    def selectRank(self, num, isInSix):
        baseChar = ''
        baseCount = 0
        r = 0
        if num == 0:
            return
        if num >= 1 and num < 5:
            baseChar = 'I'
            baseCount = num
            if isInSix:
                self.s += 'IV'
                r = num % 4
        elif num >= 5 and num < 10:
            baseChar = 'V'
            baseCount = num // 5
            r = num % 5
            if isInSix:
                self.s += 'IX'
                r = num % 9
                baseCount = num // 1
        elif num >= 10 and num < 50:
            baseChar = 'X'
            baseCount = num // 10
            r = num % 10
            if isInSix:
                self.s += 'XL'
                r = num % 40
        elif num >= 50 and num < 100:
            baseChar = 'L'
            baseCount = num // 50
            r = num % 50
            if isInSix:
                self.s += 'XC'
                r = num % 90
                baseCount = num // 10
        elif num >= 100 and num < 500:
            baseChar = 'C'
            baseCount = num // 100
            r = num % 100
            if isInSix:
                self.s += 'CD'
                r = num % 400
        elif num >= 500 and num < 1000:
            baseChar = 'D'
            baseCount = num // 500
            r = num % 500
            if isInSix:
                self.s += 'CM'
                r = num % 900
                baseCount = num // 100
        else:
            baseChar = 'M'
            baseCount = num // 1000
            r = num % 1000
        isInSix = self.isInstance(baseCount) # 对baseCount判断是否为6个特例中的数，如果有，说明为特例组成的，则也要用特例数字来表示。
        if not isInSix:
            self.s += baseCount*baseChar
        self.selectRank(r, self.isInstance(r))


solution = Solution()
print(solution.intToRoman(2611))


# AC
# Runtime: 92 ms, faster than 38.98% of Python3 online submissions for Integer to Roman.
# Memory Usage: 13.2 MB, less than 70.57% of Python3 online submissions for Integer to Roman.

# 花费时间，两个多小时，而且用的是笨方法。

# 下面是python3实现的快于99%的算法，LeetCode网友yuhaonanmessi提供：
# 思想：提取出每位的数字，然后分别处理。分析出4、9就是特例中的数字，其实40 400 90 900对百位、十位数字提取之后就是特例中的数字，
#      然后根据5来分段，对应范围中的50、500的范围。大于5则属于下一个段，小于5则属于此段。
# class Solution:
#     def intToRoman(self, num: int) -> str:
#         thousand = num // 1000
#         num = num - 1000 * thousand
#         handred = num // 100
#         num = num - 100 * handred
#         ten = num // 10
#         num = num - 10 * ten
#         one = num
#         thousand_str = thousand * "M"
#
#         handred_str = ""
#         if handred == 4:
#             handred_str = "CD"
#         elif handred == 9:
#             handred_str = "CM"
#         elif handred >= 5:
#             handred_str = "D" + ("C" * (handred - 5))
#         elif handred != 0:
#             handred_str = "C" * handred
#
#         ten_str = ""
#         if ten == 4:
#             ten_str = "XL"
#         elif ten == 9:
#             ten_str = "XC"
#         elif ten >= 5:
#             ten_str = "L" + ("X" * (ten - 5))
#         elif ten != 0:
#             ten_str = "X" * ten
#
#         one_str = ""
#         if one == 4:
#             one_str = "IV"
#         elif one == 9:
#             one_str = "IX"
#         elif one >= 5:
#             one_str = "V" + ("I" * (one - 5))
#         elif one != 0:
#             one_str = "I" * one
#
#         result = thousand_str + handred_str + ten_str + one_str
#         return result
